package tencent.st2;

import tencent.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class Solution {
//已知一个二叉树的先序遍历序列和中序遍历序列，但其中一些节点的值可能相同。请你返回所有满足条件的二叉树。二叉树在数组中的顺序是任意的。
//输入例子1:
//        [1,1,2],[1,2,1]
//输出例子1:
//        [{1,1,#,#,2},{1,#,1,2}]
    public ArrayList<TreeNode> getBinaryTrees (ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
        return buildTree2(preOrder,0, preOrder.size()-1, inOrder, 0 , inOrder.size()-1);
    }
    public ArrayList<TreeNode> buildTree2(ArrayList<Integer> preorder, int preL, int preR,
                               ArrayList<Integer> inorder, int inL, int inR) {
        ArrayList<TreeNode> result=new ArrayList<>();
        if(preL > preR || inL > inR){
            result.add(null);
            return result;
        }
        int mid = preorder.get(preL);
        int midIndex = inL;
        while(midIndex<=inR){
            if(inorder.get(midIndex) == mid){
                ArrayList<TreeNode> leftlist=buildTree2(preorder, preL+1, preL+midIndex-inL, inorder, inL, midIndex-1);
                ArrayList<TreeNode> rightlist=buildTree2(preorder,preL+midIndex-inL+1, preR, inorder, midIndex+1, inR);
                for (TreeNode treeNode : leftlist) {
                    for (TreeNode treeNode1 : rightlist) {
                        TreeNode root = new TreeNode(mid);
                        root.left = treeNode;
                        root.right = treeNode1;
                        result.add(root);
                    }
                }
            }
            midIndex++;
        }
        return result;
    }
    public static void main(String[] args) {
        Solution a = new Solution();
        ArrayList<Integer> pre=new ArrayList<>();
        pre.add(1);
        pre.add(1);
        pre.add(2);
        ArrayList<Integer> in=new ArrayList<>();
        in.add(1);
        in.add(2);
        in.add(1);
        ArrayList<TreeNode> result=a.getBinaryTrees(pre,in);
        System.out.println(result);
    }
}
